// 前序：根节点 --> 左节点--> 右节

// 解法1： 递归
function preorderTraversal(root: TreeNode | null): number[] {
    if(!root){
        return []
    }
    const res = [];

    const preOrder = (node: TreeNode | null) =>{
        if(!node){
            return;
        }
        res.push(node.val);
        preOrder(node.left);
        preOrder(node.right);
    }
    preOrder(root);
    return res;
};
// 解法2 ： 迭代
function preorderTraversal2(root: TreeNode | null): number[] {
    if(!root){
        return [];
    }
    const res = [];
    // stack用于维护遍历到的节点
    const stack: TreeNode[] = [];
    while(root || stack.length){
        // 如果有节点，就获取这个节点的数据，然后把这个节点放入栈中。然后遍历当前节点的左节点。
        if(root){
            res.push(root.val);
            stack.push(root);
            root = root.left;
        // 如果没有root，就从栈中取出一个元素，然后遍历它的右节点
        }else{
            root = stack.pop();
            root = root.right
        }
    }
    return res;
};

// 解法3： Morris遍历，有一种巧妙的方法可以在线性时间内，只占用常数空间来实现前序遍历。Morris 遍历的核心思想是利用树的大量空闲指针，实现空间开销的极限缩减。
// 其前序遍历规则总结如下：
// 1. 新建临时节点，令该节点为root，
// 2. 如果当前节点的左子节点为空，将当前节点加入答案中，并且遍历当前节点的右子节点
// 3. 如果当前节点的左子节点不为空，在当前节点的左子树中，找到当前节点在中序排序下的前驱节点。
//  3.1 如果前驱节点的右子节点为空，则将前驱界定的右子节点设置为当前节点。然后将当前节点加入答案，并将前驱节点的右子节点更新为当前节点。当前节点更新为当前节点的左子节点。
//  3.2如果前驱节点的右子节点为当前节点，将它的右子节点重新设置为空。当前节点更新为当前节点的右子节点。
// 4. 重复2，3，知道遍历结束

function preorderTraversal3(root: TreeNode | null): number[] {
    if(!root){
        return [];
    }
    const res = [];
    // 前驱节点
    let predecessor:TreeNode = null;
    while(root){
        if(!root.left){
            res.push(root.val);
            root = root.right;
        }else{
            predecessor = root.left;
            while(predecessor.right && predecessor.right!== root){
                predecessor = predecessor.right;
            }
            if(!predecessor.right){
                predecessor.right = root;
                res.push(root.val);
                root = root.left;
            }else if(predecessor.right === root){
                predecessor.right = null;
                root = root.right
            }
        }
    }
    return res
};